package com.wtpaint.algorithm.sort;

import com.wtpaint.algorithm.SortUtil;

import java.util.Arrays;

/**
 * 实现一个链表  实现自底向上的归并...
 */
public class MergeSort {

    private MergeSort() {
    }

    public static void sort(Comparable[] arr) {
        int n = arr.length;
        mergeSort(arr, 0, n - 1);
    }

    //递归使用归并，对arr[start,end]的范围内进行排序
    private static void mergeSort(Comparable[] arr, int start, int end) {
        //递归到底
//        if (start >= end) {
//            return;
//        }
        //优化2：插入排序进行优化
        if (end - start <= 15) {
            insertionSort(arr, start, end);
            return;
        }

        //1、取中间值
        int mid = start + (end - start) / 2;

        //2、递归
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);

        //3、归并
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {//优化1：对近乎有序的数据
            merge(arr, start, mid, end);
        }
    }

    private static void merge(Comparable[] arr, int start, int mid, int end) {
        //开辟一个临时空间
        Comparable[] temp = new Comparable[end - start + 1];
        for (int i = start; i <= end; i++) {
            temp[i - start] = arr[i];
        }

        int i = start, j = mid + 1;
        for (int k = start; k <= end; k++) {
            //判断索引的合法性
            if (i > mid) {
                arr[k] = temp[j - start];
                j++;
            } else if (j > end) {
                arr[k] = temp[i - start];
                i++;
            }
            //比较两个值进行merge
            else if (temp[i - start].compareTo(temp[j - start]) < 0) {
                arr[k] = temp[i - start];
                i++;
            } else {
                arr[k] = temp[j - start];
                j++;
            }
        }
    }

    public static void insertionSort(Comparable[] arr, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            Comparable temp = arr[i];
            int j;
            for (j = i; j > start && arr[j - 1].compareTo(temp) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    public static void main(String[] args) {
        int n = 20000;
        Integer[] arr = SortUtil.generateRandomArray(n, 0, 2);
        SortUtil.printArray(arr);
        Integer[] arr2 = Arrays.copyOf(arr, arr.length);
        SortUtil.testSort("com.wtpaint.algorithm.sort.MergeSort", arr);
        SortUtil.testSort("com.wtpaint.algorithm.sort.InsertionSort", arr2);
        SortUtil.printArray(arr);
        SortUtil.printArray(arr2);
    }


}
